﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CriptoHash.Criptografia
{
    public class Matematica
    {
        private static SortedDictionary<int, int> dicionarioPrimos;

        static Matematica()
        {
            dicionarioPrimos = new SortedDictionary<int, int>();

            #region Iniciar alguns valores de primos default
            dicionarioPrimos.Add(2, 2);
            dicionarioPrimos.Add(3, 3);
            dicionarioPrimos.Add(5, 5);
            dicionarioPrimos.Add(7, 7);
            dicionarioPrimos.Add(11, 11);
            dicionarioPrimos.Add(13, 13);
            dicionarioPrimos.Add(17, 17);
            #endregion
        }

        /// <summary>
        ///     Apenas parra números primos não negativos e diferentes de 0
        /// </summary>
        /// <param name="numero"></param>
        /// <returns>Se um determinado número é primo ou não</returns>
        public static bool Primo(int numero)
        {
            //Aceitamos o 1 como primo
            if (numero == 1)
            {
                return true;
            }
            //Valores menores que 1 não são primos
            if (numero < 1)
            {
                return false;
            }

            int metadeNumero = (int)Math.Floor((double)numero / 2);

            if (dicionarioPrimos.Count == 0)
            {
                //O número é dividido até a metade dele, caso não existam divisores, ele é primo
                for (int i = 2; i <= metadeNumero; i++)
                {
                    if (numero % i == 0)
                    {
                        return false;
                    }
                }

                //Ele não é primo e será adicionado ao dicionário
                dicionarioPrimos.Add(numero, numero);

                return true;
            }
            else
            {
                //Se ele já consta no dicionário de primos, logo o resultado é verdadeiro
                if (dicionarioPrimos.ContainsValue(numero))
                {
                    return true;
                }
                else
                {
                    int maiorPrimo = MaiorPrimoDicionario();

                    //Se ele é maior que o maior dos primos no dicionário, vamos dividí-lo por todos
                    //os primos que constam no dicionário e depois dividí-lo por todos os números entre
                    //o maior dos primos e a metade dele
                    if (metadeNumero > maiorPrimo)
                    {
                        //Primeiro dividindo por todos os primos até então
                        foreach (KeyValuePair<int, int> entry in dicionarioPrimos)
                        {
                            //Se ele for divisível por algum deles, ele não é primo
                            if (numero%entry.Value == 0)
                            {
                                return false;
                            }
                        }

                        //Caso ele não seja divisível por nenhum dos primos anteriores
                        //Vamos dividí-lo por todos os números do maior primo até a metade dele

                        for (int i = maiorPrimo; i < metadeNumero; i++)
                        {
                            if (numero % i == 0)
                            {
                                return false;
                            }
                        }

                        //Caso não tenham sido encontrado divisores, ele é adicionado a lista e é primo
                        dicionarioPrimos.Add(numero, numero);

                        return true;
                    }
                    else
                    {
                        //Se a metade dele não é maior que o maior dos primos, então primeiro vamos
                        //dividí-lo por todos os primos da lista que sejam menores que ele

                        foreach (KeyValuePair<int, int> entry in dicionarioPrimos)
                        {
                            //Se ele for divisível por algum deles, ele não é primo
                            if (entry.Value < metadeNumero)
                            {
                                if (numero % entry.Value == 0)
                                {
                                    return false;
                                }
                            }
                            else
                            {
                                break;
                            }
                        }

                        //Agora vamos dividí-lo por todos os valores entre o 2 e sua metade, o método tradicional
                        for (int i = 2; i < metadeNumero; i++)
                        {
                            if (numero % i == 0)
                            {
                                return false;
                            }
                        }

                        //Caso não tenham sido encontrado divisores, ele é adicionado a lista e é primo
                        dicionarioPrimos.Add(numero, numero);

                        return true;
                    }
                }
            }
        }

        private static int MaiorPrimoDicionario()
        {
            int maior = int.MinValue;

            foreach (KeyValuePair<int, int> entry in dicionarioPrimos)
            {
                if (entry.Value > maior)
                {
                    maior = entry.Value;
                }
            }

            return maior;
        }

        /// <summary>
        ///     Método para verificar tradicionalmente se um número é primo ou não. Só funciona para
        ///     números maiores que 1.
        /// </summary>
        /// <param name="numero"></param>
        /// <returns></returns>
        public static bool PrimoTradicional(int numero)
        {
            int metadeNumero = (int)Math.Floor((double)numero / 2);

            for (int i = 2; i <= metadeNumero; i++)
            {
                if (numero % i == 0)
                {
                    return false;
                }
            }

            return true;
        }

        /// <summary>
        ///     Retorna  o maior número primo que seja menor que o número passado
        /// </summary>
        /// <param name="numero"></param>
        /// <returns></returns>
        public static int MenorPrimo(int numero)
        {
            //Primeiro vamos achar o maior número primo (do dicionário) menor que o número

            int maiorPrimo = -1;

            foreach (KeyValuePair<int, int> entry in dicionarioPrimos)
            {
                if (entry.Value > maiorPrimo && entry.Value < numero)
                {
                    maiorPrimo = entry.Value;
                }

                //Se a lista já ficar maior do que o número, paramos o for
                if (entry.Value > numero)
                {
                    break;
                }
            }
            
            //Depois de pegar o maiorPrimo do dicionário menor que o número, vamos 
            //Veriicar todos os números a partir dele, em ordem decrescente, até o maiorPrimo
            //Para pegar o maior primo, caso não existam primos até o maiorPrimo, ele será o resultado

            int maiorPrimoAchado = -1;

            for (int i = numero - 1; i > maiorPrimo; i--)
            {
                //O primeiro primo achado já será o resultado, porque a busca é decrescente
                if (Primo(i))
                {
                    maiorPrimoAchado = i;
                    break;
                }
            }

            //Se for achado algum primo
            if (maiorPrimoAchado != -1)
            {
                return maiorPrimoAchado;
            }
            //Se não, então o resultado é o maiorPrimo
            else
            {
                return maiorPrimo;
            }
        }

        /// <summary>
        ///     Dado dois números, eles são primos entre si se não forem simultaneamente divisíveis por nenhum número diferente de 1
        /// </summary>
        /// <param name="numeroA"></param>
        /// <param name="numeroB"></param>
        /// <returns></returns>
        public static bool PrimosEntreSi(int numeroA, int numeroB)
        {
            int menor = (numeroA > numeroB) ? numeroB : numeroA;
            int maior = (numeroA > numeroB) ? numeroA : numeroB;

            for (int i = 2; i <= menor; i++)
            {
                if (menor % i == 0 && maior % i == 0)
                {
                    return false;
                }
            }

            return true;
        }
    }
}
